﻿package fr.chrysalis.utils
{

	public class DLinkedList 
	{
		
		/**
		 * Première node 
		 */
		private var _head:DLinkedListNode;
		/**
		 * Dernière node 
		 */
		private var _tail:DLinkedListNode;
		/**
		 * Nombre d'élément dans la list 
		 */
		private var _length:Number = 0;
		/**
		 * Class des nodes 
		 */
		private var _nodeClass:Class;
		
		/**
		 * Création d'une liste 
		 * @param nodeClass Classe personalisée pour les nodes
		 */
		public function DLinkedList(nodeClass:Class = null):void
		{
			_nodeClass = (nodeClass == null)? DLinkedListNode:nodeClass;
		}
		/**
		 * Récupération du premier élément
		 * @return 
		 */
		public function get first():DLinkedListNode
		{
			return (_head.next == _tail)? null:_head.next;
		}
		/**
		 * Récupération du dernier élément
		 * @return 
		 */
		public function get last():DLinkedListNode
		{
			return (_tail.prev == _head)? null:_head;
		}
		
		/**
		 * Récupération du tail 
		 * @return 
		 */
		public function get tail():DLinkedListNode
		{
			return _tail;
		}
		/**
		 * Récupération du head 
		 * @return 
		 */
		public function get head():DLinkedListNode
		{
			return _head;
		}
		
		/**
		 * Récupération de la longueur de la liste 
		 * @return 
		 */
		public function get length():Number
		{
			return _length;
		}
		
		/**
		 * Création d'un node en fonction du type passé en paramètre 
		 * @param value Data à "noder"
		 * @return node crée
		 */
		private function makeNode(value:*):DLinkedListNode
		{
			var node:DLinkedListNode;
			if(value is DLinkedListNode)
			{
				node = value;
			}
			else
			{
				node = new _nodeClass(value);
			}
			return node;
		}
		
		/**
		 * Insertion d'une valeur apres une node spécifique 
		 * @param value Valeur à insérer
		 * @param prev Node précédente
		 * @return Node crée
		 */
		public function insertAfter(value:*,prev:DLinkedListNode):DLinkedListNode
		{
			var node:DLinkedListNode = makeNode(value);
			node.prev = prev;
			node.next = prev.next;
			node.prev.next = node;
			node.next.prev = node;
			
			_length++;
			return node;
		}
		
		/**
		 * Récupère la node associée à la valeur
		 * @param value Valeur à rechercher
		 * @return Node trouvée
		 */
		public function getNode(value:*):DLinkedListNode
		{
			if(value is DLinkedListNode)
				return value;
			else
			{
				return find(value);
			}
		}
		
		/**
		 * Récupère la node associée à la valeur
		 * @param Valeur à rechercher
		 * @return  Node trouvée
		 */
		public function find(value:*):DLinkedListNode
		{
			var cur:DLinkedListNode = _head;
			while(cur.value != value && cur != _tail)
				cur = cur.next;
			return (cur == _tail)? null:cur;
		}
		
		/**
		 * Supprime la node associé à la valeur 
		 * @param value data à supprimer
		 * @return Node supprimée
		 */
		public function remove(value:*):DLinkedListNode
		{
			var node:DLinkedListNode = getNode(value);
			node.prev.next = node.next;
			node.next.prev = node.prev;			
			_length--;
			return node;
		}
		
		/**
		 * Insert une valeur à la fin de la liste 
		 * @param value valeur à insérer
		 * @return node crée
		 */
		public function push(value:*):DLinkedListNode
		{
			
			var node:DLinkedListNode = makeNode(value);
			// add the clip to the list
			if (head)
			{
				_tail.next	= node ; 
				node.prev	= _tail ;
				_tail		= node ;
			}
			else
				_head = _tail = node;
			
			++_length;
			
			return node;
		}
		
		/**
		 * Supprime la dernière valeur 
		 * @return node supprimée
		 */
		public function pop():DLinkedListNode
		{
			return (_length == 0)? null:remove(_tail.prev);	
		}
		
		/**
		 * Insert une valeur au début de la liste 
		 * @param value valeur à insérer
		 * @return node crée
		 */
		public function unshift(value:*):DLinkedListNode
		{
			return insertAfter(value,_head);
		}
		
		/**
		 * Supprime la première valeur 
		 * @return node supprimée
		 */
		public function shift():DLinkedListNode
		{
			return (_length == 0)? null:remove(_head.next);
		}
		
		/**
		 * Debug 
		 */
		public function dump():void
		{
			var output:String,
				node:DLinkedListNode;
				
			output = " List Content ( "+ this._length + " elems ) : \n";
				
			if (!head) {
				Debug.dump("Vide");
			}
			
			node = head.next;
			
			Debug.dump("head : " + head.value);
			while (node && (node != tail) )
			{
				output += Debug.dump("node : " + node.value);
				node = node.next;
			}
			if (head != tail) {
				Debug.dump("tail : " + tail.value);
			}
		}
		
	}
	
}